﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int min(int x,int y)
{
	return x < y ? x : y;
}
/*
======================================================================================================================================
描述
给定一个二维数组map，含义是一张地图

游戏的规则如下:
1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?
根据map,输出初始血量。

输入描述：
第一行两个正整数n，m ,1≤n,m≤1000
 ，接下来n行，每行m个整数，代表map−10 

输出描述：
输出一个整数，表示答案。
=======================================================================================================================================
*/
int main()
{
	int m = 0, n = 0;
	scanf("%d%d", &m, &n);
	int** arr = (int**)malloc(n * sizeof(int*));
	int** dp = (int**)malloc(n * sizeof(int*));
	for (int i = 0; i < n; i++)                //创建数组和dp数组
	{
		arr[i] = (int*)malloc(m * sizeof(int));
		dp[i] = (int*)malloc(m * sizeof(int));
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	if (arr[n - 1][m-1] > 0)                           //给dp数组赋初值，血瓶则赋值为1，使得最小
	{
		dp[n - 1][m - 1] = 1;
	}
	else                                               //怪物则赋值使高1滴血
	{
		dp[n - 1][m - 1] = -arr[n - 1][m - 1] + 1;
	}
	for (int i = m-2; i >= 0; i--)                      //初始化最后一行
	{
		if (dp[n - 1][i + 1] - arr[n - 1][i] > 0)
		{
			dp[n - 1][i] = dp[n - 1][i + 1] - arr[n - 1][i];
		}
		else
		{
			dp[n - 1][i] = 1;
		}
	}
	for (int i = n - 2; i >= 0; i--)                    //初始化最后一列
	{
		if (dp[i+1][m-1] - arr[i][m-1] > 0)
		{
			dp[i][m-1] = dp[i+1][m-1] - arr[i][m-1];
		}
		else
		{
			dp[i][m-1] = 1;
		}
	}
	for (int i = n - 2; i >= 0; i--)                        //遍历求dp数组
	{
		for (int j = m - 2; j >= 0; j--)
		{
			int Min= min(dp[i][j + 1], dp[i + 1][j]);       //找出走到下一格且能走到终点所需最小血量
			if (Min - arr[i][j] > 0)                        //这个血量比当前事件大
			{
				dp[i][j] = Min - arr[i][j];                 //当前格到终点所需最低血量即为差值
			}
			else                                            //比当前事件小
			{
				dp[i][j] = 1;                               //置1
			}
		}
	}
	printf("%d", dp[0][0]);
	free(arr);
	free(dp);
	return 0;
}